/**
  * LSP MD5 Atmiņas izdalīšana
  *
  * Andrejs Bogdanovs
  * Maksims Savčuks
  * Aleksejs Smišļajevs
  */
#include <stdlib.h> // malloc()
#include <stdio.h>
#include <string.h> // strcmp(), memcpy()
#include <time.h>   // clock_gettime(), CLOCK_MONOTONIC

#define MEM_SIZE 1024   // maximum amount of memory
int CHUNKS[MEM_SIZE];   // chunk count can't exceed 1024 (worst case 1byte*MEM_SIZE)
int iCHUNKS = 0;        // total count of chunks created
int SIZES[MEM_SIZE];    // assume memory can't be freed: cannot request
                        //     memory allocation more than MEM_SIZE times (by 1byte)
int iSIZES = 0;         // total count of requested sizes

double find_frag(int* data) {
    /* calculate fragmentation of data
     * fragmentation = 1 - (largest free chunk) / (total amount of free space)
     *
     * @param data: array of chunks after request allocation
     * @return: fragmentation
     */
    int max = 0;
    int total = 0;
    int i;
    for(i = 0; i < iCHUNKS; i++) {
        total += data[i];
        if(data[i] > max) {
            max = data[i];
        }
    }
    return (total > 0 ? 1 - (double)max / total : 0);
}

double best_fit(void) {
    /* apply BestFit strategy for the CHUNKS
     *
     * find a chunk with the smallest leftover after allocation
     * (try to fit requested sizes between already allocated chunks)
     *
     * @return: fragmentation after BestFit application
     */
    int chunks[iCHUNKS];    // copy to local array to not mess up
                            // CHUNKS is used by three more functions
    memcpy(chunks, CHUNKS, iCHUNKS*sizeof(int));
    int i;
    int j;
    int diff; // difference between chunk size and requested size
    for(i = 0; i < iSIZES; i++) {
        int best_diff = 1024; // best found difference (maximal at the start)
        int best_index = -1; // index of the best match
        for(j = 0; j < iCHUNKS; j++) {
            diff = chunks[j] - SIZES[i];
            if(diff == 0) {
                // perfect fit
                best_index = j;
                break;
            } else if((diff < best_diff) && (diff > 0)) {
                // found better fit with smaller difference
                // save found chunk
                best_index = j;
                best_diff = diff;
            }
        }
        // check that place was actually found
        if(best_index != -1) {
            // decrease chunk size
            chunks[best_index] -= SIZES[i];
            // reset index
            best_index = -1;
        } else {
            printf("BestFit: Not enough space to allocate %3d bytes. "
                "Skipping.\n", SIZES[i]);
        }
    }
    return find_frag(chunks);
}

double first_fit() {
    /* apply FirstFit strategy for the CHUNKS
     *
     * find a first chunk, that can fit the requested size
     *
     * @return: fragmentation after FirstFit application
     */
    int data[iCHUNKS];
    int i=0;
    int j=0;
    int flag=0;
    memcpy(data, CHUNKS, iCHUNKS*sizeof(int));
    for(i=0; i<iSIZES; i++) {
        for(j=0; j<iCHUNKS; j++) {
            if(data[j] >= SIZES[i]) {
                // if it fits, allocate and continue to next request
                data[j]-=SIZES[i];
                flag = 1;
                break;
            }
        }
        if(flag) {
            flag = 0;
        } else {
            printf("FirstFit: Not enough space to allocate %3d bytes. "
                "Skipping.\n", SIZES[i]);
        }
    }
    return find_frag(data);
}

double worst_fit() {
    /* apply WorstFit strategy for the CHUNKS
     *
     * find a chunk, where the leftover after allocating a request is the largest
     *
     * @return: fragmentation afret WorstFit application
     */
    int chunks[iCHUNKS];
    memcpy(chunks, CHUNKS, iCHUNKS*sizeof(int));
    int i;
    int j;
    int diff; //dirrerence chunk size<->req. size
    for(i = 0; i < iSIZES; i++) {
        int worst_diff = 0; // worst found difference (minimal at the start)
        int worst_index = -1; //Index for best match
        for(j = 0; j < iCHUNKS; j++) {
            diff = chunks[j] - SIZES[i];
            if (diff >= worst_diff) {
                // found chunk with greater difference
                worst_index = j;
                worst_diff = diff;
            }
        }
        // check that a chunk has been found
        if (worst_index != -1) {
            chunks[worst_index] -= SIZES[i];
            worst_index = -1;
        } else {
            printf("WorstFit: Not enough space to allocate %3d bytes. "
                "Skipping.\n", SIZES[i]);
        }
    }
    return find_frag(chunks);
}

double next_fit(){
    /* apply NextFit strategy for the CHUNKS
     *
     * find next chunk (after previously allocated chunk),
     * that can fit next request.
     *
     * @return: fragmentation after NextFit application
     */
    int data[iCHUNKS];
    memcpy(data, CHUNKS, iCHUNKS*sizeof(int));
    int i;
    int j=-1;
    int flag=0;
    for(i=0; i<iSIZES; i++){
        int sPos= j; //Saving last successive search position.
        if(sPos < 0)
            sPos += iCHUNKS;
        // go until sPos reached again (full loop)
        do{
            j = (j + 1) % iCHUNKS;
            if(data[j] >= SIZES[i]){
                // found, allocate and skip to next request
                data[j]-=SIZES[i];
                flag=1;
                break;
            }
        }while(j!=sPos);
        if(flag) {
            flag = 0;
        } else {
            printf("NextFit: Not enough space to allocate %3d bytes. "
                "Skipping.\n", SIZES[i]);
        }
    }
   return find_frag(data);
}

double random_fit(){
    /* apply RandomFit strategy for the CHUNKS
     *
     * Start at random position. If it cannot contain given request,
     * apply NextFit strategy
     *
     * @return: fragmentation after NextFit application
     */
    srand(time(NULL));
    int data[iCHUNKS];
    memcpy(data, CHUNKS, iCHUNKS*sizeof(int));
    int i;
    int flag=0;
    for(i=0; i<iSIZES; i++){
        int j = (rand() % iCHUNKS) - 1;
        int sPos = j; //Saving last successive search position.
        if(sPos < 0)
            sPos += iCHUNKS;
        // go until sPos reached again (full loop)
        do{
            j = (j + 1) % iCHUNKS;
            if(data[j] >= SIZES[i]){
                // found, allocate and skip to next request
                data[j]-=SIZES[i];
                flag=1;
                break;
            }
        }while(j!=sPos);
        if(flag) {
            flag = 0;
        } else {
            printf("RandomNextFit: Not enough space to allocate %3d bytes. "
                "Skipping.\n", SIZES[i]);
        }
    }
   return find_frag(data);
}

double hardcore_fit() {
    /* apply hardcore RandomFit strategy for the CHUNKS
     *
     * Choose some chunk randomly.
     * If it's already been checked, go and find next random chunk.
     * Continue until unchecked chunk is found or all chunks are checked
     *
     * @return: fragmentation after NextFit application
     */
    int chunks[iCHUNKS];
    memcpy(chunks, CHUNKS, iCHUNKS*sizeof(int));
    int i;
    int j; //Counts times we go through checked chunks array
    int rand_pos;
    int chkd_count = 0;
    int flag = 0;
    int chunk_chkd[iCHUNKS]; //To store info about checked blks

    srand(time(NULL));

    for (i = 0; i < iSIZES; i++) {
        //All blocks are unchecked at start
        memset(chunk_chkd, 0, iCHUNKS*sizeof(int));
        chkd_count = 0;

        do {
            rand_pos = rand() % iCHUNKS;
            // if not checked this yet
            if(!chunk_chkd[rand_pos]) {
                // check size
                if(chunks[rand_pos] >= SIZES[i]) {
                    chunks[rand_pos] -= SIZES[i];
                    flag = 1;
                }
                // mark checked
                chunk_chkd[rand_pos] = 1;
                chkd_count++;
            }
        }while(!flag && (chkd_count < iCHUNKS));

        if (flag) {
            flag = 0;
        } else {
            printf("RandomHcFit: Not enough space to allocate %3d bytes. "
                "Skipping.\n", SIZES[i]);
        }
    }
    return find_frag(chunks);
}
int main(int argc, char* argv[]) {
    if(argc != 5) {
        printf("Invalid argument count passed. Aborting.\n"
            "Expected:\n"
            "    ./md5 -c CHUNKS_FILENAME -s SIZES_FILENAME\n");
        return -1;
    }
    int get_chunks = 0;
    int get_sizes = 0;
    char* chunks;
    char* sizes;
    int i;
    for(i = 0; i < argc; i++) {
        if(!strcmp(argv[i], "-c")) {
            // assume next arg is chunks filename
            get_chunks = 1;
        } else if(!strcmp(argv[i], "-s")) {
            // assume next arg is sizes filename
            get_sizes = 1;
        } else if(get_chunks) {
            if(get_sizes) {
                // assuming both filenames - messeg arg order
                printf("Invalid arguments passed. Aborting.\n"
                    "Expected:\n"
                    "    ./md5 -c CHUNKS_FILENAME -s SIZES_FILENAME\n"
                    "or:\n"
                    "    ./md5 -s SIZES_FILENAME -c CHUNKS_FILENAME\n");
                return -1;
            }
            chunks = argv[i];
            // not assuming chunks anymore
            get_chunks = 0;
        } else if (get_sizes) {
            sizes = argv[i];
            // not assuming sizes anymore
            get_sizes = 0;
        }
    }
    FILE* chunk_file;
    if((chunk_file = fopen(chunks, "r")) == NULL) {
        printf("Could not open CHUNKS file: '%s'. Aborting.\n", chunks);
        return -1;
    }
    FILE* sizes_file;
    if((sizes_file = fopen(sizes, "r")) == NULL) {
        printf("Could not open SIZES file: '%s'. Aborting.\n", sizes);
        return -1;
    }
    int chunk_length;
    // read all chunks and sizes into arrays
    while(fscanf(chunk_file, "%d\n", &chunk_length) == 1) {
        CHUNKS[iCHUNKS++] = chunk_length;
    }
    fclose(chunk_file);
    while(fscanf(sizes_file, "%d\n", &chunk_length) == 1) {
        SIZES[iSIZES++] = chunk_length;
    }
    fclose(sizes_file);

    // *_frag for fragmentation measurement
    // *_time for time measurement
    double best_frag;
    struct timespec best_time;
    double worst_frag;
    struct timespec worst_time;
    double first_frag;
    struct timespec first_time;
    double next_frag;
    struct timespec next_time;
    double random_frag;
    struct timespec random_time;
    double hardcore_frag;
    struct timespec hardcore_time;
    struct timespec test_time;

    char fmt[80];
    char buffer[80*6];  // test output buffer (4 lines * 80 chars)
    buffer[0] = '\0';

    // test best_fit()
    // save test_time
    clock_gettime(CLOCK_MONOTONIC, &test_time);
    // run allocation, receive fragmentation measurement
    best_frag = best_fit();
    // save best_time
    clock_gettime(CLOCK_MONOTONIC, &best_time);
    sprintf(buffer, "%sBestFit results:\ttime: %ldns\tfragmentation: %f\n",
        buffer, best_time.tv_nsec - test_time.tv_nsec, best_frag);

    // test worst_fit()
    clock_gettime(CLOCK_MONOTONIC, &test_time);
    worst_frag = worst_fit();
    clock_gettime(CLOCK_MONOTONIC, &worst_time);
    sprintf(buffer, "%sWorstFit results:\ttime: %ldns\tfragmentation: %f\n",
        buffer, worst_time.tv_nsec - test_time.tv_nsec, worst_frag);

    // test first_fit()
    clock_gettime(CLOCK_MONOTONIC, &test_time);
    first_frag = first_fit();
    clock_gettime(CLOCK_MONOTONIC, &first_time);
    sprintf(buffer, "%sFirstFit results:\ttime: %ldns\tfragmentation: %f\n",
        buffer, first_time.tv_nsec - test_time.tv_nsec, first_frag);

    // test next_fit()
    clock_gettime(CLOCK_MONOTONIC, &test_time);
    next_frag = next_fit();
    clock_gettime(CLOCK_MONOTONIC, &next_time);
    sprintf(buffer, "%sNextFit results:\ttime: %ldns\tfragmentation: %f\n",
        buffer, next_time.tv_nsec - test_time.tv_nsec, next_frag);

    // test hardcore_fit()
    clock_gettime(CLOCK_MONOTONIC, &test_time);
    hardcore_frag = hardcore_fit();
    clock_gettime(CLOCK_MONOTONIC, &hardcore_time);
    sprintf(buffer, "%sRandomHcFit results:\ttime: %ldns\tfragmentation: %f\n",
        buffer, hardcore_time.tv_nsec - test_time.tv_nsec, hardcore_frag);

    // test random_fit()
    clock_gettime(CLOCK_MONOTONIC, &test_time);
    random_frag = random_fit();
    clock_gettime(CLOCK_MONOTONIC, &random_time);
    sprintf(buffer, "%sRandomNextFit results:\ttime: %ldns\tfragmentation: %f\n",
        buffer, random_time.tv_nsec - test_time.tv_nsec, random_frag);

    printf("%s", buffer);
    return 0;
}
